package main
//给定整数 n 和 k，返回 [1, n] 中字典序第 k 小的数字。
//
//
//
// 示例 1:
//
//
//输入: n = 13, k = 2
//输出: 10
//解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。
//
//
// 示例 2:
//
//
//输入: n = 1, k = 1
//输出: 1
//
//
//
//
// 提示:
//
//
// 1 <= k <= n <= 10⁹
//
//
// Related Topics 字典树 👍 567 👎 0

// leetcode submit region begin(Prohibit modification and deletion)
package main

func findKthNumber(n int, k int) int {
	i := 1

	for {
		treeNum := count(i, n)
		if k > treeNum {
			k = k - treeNum
			i++
		} else {
			if k > 1 {
				i *= 10
				k--
			} else {
				break
			}
		}
	}
	return i
}

func count(i, n int) int {
	j := i + 1
	count := 0
	for i <= n {
		count += min(j-1, n) - i + 1
		j = j * 10
		i = i * 10
	}
	return count
}



//leetcode submit region end(Prohibit modification and deletion)
